/**
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 * 二叉树的层序遍历
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * @param root
 */
const levelOrder = (root: TreeNode | null): number[][] => {
  // 边界判断
  if (root === null) return [];

  const ans: number[][] = [];

  const stack: TreeNode[] = [];

  // 先把root放入栈中
  stack.push(root);

  const cur: number[] = []
  let level = 1

  while (stack.length !== 0) {
    const n = stack.pop()!;
    // 当前的层数减1
    level--
    cur.push(n.val)

    // 左子树不为空
    if (n.left !== null) stack.push(n.left);

    // 右子树不为空
    if (n.right !== null) stack.push(n.right);

    if (level === 0) {
        // 当前层已经遍历完了
        // 更新level
        level = stack.length;

        // 收集结果
        ans.push([...cur])

        // 清空cur
        cur.length = 0
    }

  }

  return ans
};
